package leetcode.code0785;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public boolean isBipartite(int[][] graph) {
		int n = 101;
		int[] cnts = new int[n];
		for (int u = 0; u < graph.length; u++) {
			if (cnts[u] == 0) {
				Queue<Integer> queue = new LinkedList<>();
				queue.add(u);
				int cnt = 1;
				while (!queue.isEmpty()) {
					int size = queue.size();
					while (size > 0) {
						int cur = queue.poll();
						cnts[cur] = cnt;
						int[] g = graph[cur];
						for (int i = 0; i < g.length; i++) {
							int v = g[i];
							if (cnts[v] != 0) {
								if (((cnt - cnts[v]) & 1) == 0) {
									return false;
								}
							} else {
								queue.add(g[i]);
							}
						}
						size--;
					}
					cnt++;
				}
			}
		}
		return true;
	}

	@Override
	public void debug4() {
		H.compare(false, this.isBipartite(H.str2array1("[[4,1],[0,2],[1,3],[2,4],[3,0]]")));
		H.compare(true, this.isBipartite(H.str2array1("[[1,3],[0,2],[1,3],[0,2]]")));
		H.compare(false, this.isBipartite(H.str2array1("[[1,2,3],[0,2],[0,1,3],[0,2]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
